#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1050;
//跟01背包一样可以压缩为一维数组
int dp[MAXN];
int main(void){
    int ans;
	int m=5;
	int a[]={1,4,2,5,-12};
	int n=4;
	int b[]={-12,1,2,4};
	for(int i=0;i<m;i++){
		int len=0;
		for(int j=0;j<n;j++){
			//这部分更新dp[j]
			//因为是公共子序列所以只要用b[j]来保存这个公共子序列的最后一个元素
			//所以这里a[i]和b[j]比较其实也是和整个公共子序列比较，如果是递增
			//则暂时增加len，然后接下来的b[j]循环中如果出现相同的，该LICS就成立，dp就等于len+1
			if(a[i]>b[j]){
                // 注意这两个max
				len=max(len,dp[j]);
			}
			//如果两个数相同，说明在前一步的len的基础上再加1，用max保证更优
			else if(a[i]==b[j]){
                // 注意这两个max
				dp[j]=max(dp[j],len+1);
			}
			//更新答案
			ans=max(ans,dp[j]);
		}
	}
	return 0;
}
